package leetcode.hash和set;

import java.util.*;

/**
 * 两个数组的交集 II
 *
 * 给定两个数组，编写一个函数来计算它们的交集。(允许包含重复的元素)
 *
 * 总体时间复杂度：O(n)
 * 空间复杂度：S(n)
 */
public class Test350两个数组的交集II {

    public static int[] intersect(int[] nums1, int[] nums2) {
        // map 记录 nums1 里面的元素以及出现的频率
        // O(n)  ==> 遍历数组是 n，往 map 里面插入数据是 1
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums1.length; i++) {
            if (map.containsKey(nums1[i])) {
                map.put(nums1[i], map.get(nums1[i])+1);
            } else {
                map.put(nums1[i], 1);
            }

        }

        List<Integer> list = new ArrayList<>();

        // 然后遍历 nums2，如果 map 里面有 nums2 里面的数据就表示符合要求
        // 取出该数据存储到 list 里面，同时将该数据出现的次数 - 1（nums2 后面可能再次遇到该 nums2[i]）
        for (int i = 0; i < nums2.length; i++) {
            if (map.containsKey(nums2[i]) && map.get(nums2[i]) > 0) {
                list.add(nums2[i]);
                map.put(nums2[i], map.get(nums2[i])-1);
            }
        }

        // 对象转数组
        Object[] a = list.toArray();
        int i = 0;
        int[] ans = new int[a.length];
        for (Object e: a) {
            ans[i++] = (int) e;
        }
        return ans;
    }

    public static void main(String[] args) {
        int[] nums1 = new int[]{1,2,2,2,2,1};
        int[] nums2 = new int[]{2,2,2};
        int[] ans = intersect(nums1, nums2);

        Integer[] ans2 = intersection3(nums1, nums2);

        System.out.println(Arrays.toString(ans));
        System.out.println(Arrays.toString(ans2));
    }

    // 第二种解法：使用排序【更好的做法】
    public static int[] intersect2(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int i = 0;
        int j = 0;
        List<Integer> list = new ArrayList<>(nums1.length);
        while (i < nums1.length && j < nums2.length) {
            if (nums1[i] == nums2[j]) {
                list.add(nums1[i]);
                i++;
                j++;
            } else if (nums1[i] > nums2[j]) {
                j++;
            } else {
                i++;
            }
        }
        // 对象转数组
        Object[] a = list.toArray();
        int n = 0;
        int[] ans = new int[a.length];
        for (Object e: a) {
            ans[n++] = (int) e;
        }
        return ans;
    }


    /**
     * 求交集，就是找出 nums1 和 nums2 里面一样的数据
     *
     * @param nums1
     * @param nums2
     */
    public static Integer[] intersection3(int[] nums1, int[] nums2) {
        List<Integer> list1 = new ArrayList<>();
        List<Integer> list2 = new ArrayList<>();
        // 去重
        Arrays.stream(nums1).forEach(list1::add);
        Arrays.stream(nums2).forEach(list2::add);

        // 求交集
        list1.retainAll(list2);

        // 求差集
//        list1.removeAll(list2);


        // 求并集
//        list1.removeAll(list2);
//        list1.addAll(list2);

        Integer[] ans = list1.stream().toArray(Integer[]::new);
        return ans;
    }
}
